/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Practica7.Practica;

import Practica7.structures.BinomialQueue;
import java.util.Comparator;

/**
 *
 * @author miguel
 */
public class MyBinomialQueue<Type> extends BinomialQueue<Type> {

    private BinomialNode<Type>[] trees;
    private static int MAX_NUMBER_TREES = 100;
    private Comparator c;

    public MyBinomialQueue(Comparator<Type> comparator) {
        trees = new BinomialNode[MAX_NUMBER_TREES];
        makeEmpty();
        c = comparator;
    }

    public MyBinomialQueue(int size, Comparator<Type> comparator) {
        trees = new BinomialNode[size];
        makeEmpty();
        c = comparator;
    }

    public BinomialNode<Type>[] getTrees() {
        return trees;
    }

    public final void makeEmpty() {
        size = 0;
        for (int i = 0; i < trees.length; i++) {
            trees[i] = null;
        }
    }

    @Override
    public Type findMin() {
        if (isEmpty()) {
            return null;
        }
        return trees[findMinIndex()].element;
    }

    private int findMinIndex() {
        int i;
        int minIndex;
        for (i = 0; trees[i] == null; i++);

        for (minIndex = i; i < trees.length; i++) {
            if (trees[i] != null && c.compare(trees[i].element, trees[minIndex]) < 0) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Type deleteMin() {
        if (isEmpty()) {
            return null;
        }
        int minIndex = findMinIndex();
        Type minItem = trees[minIndex].element;
        BinomialNode deletedTree = trees[minIndex].leftChild;
        MyBinomialQueue deletedQueue = new MyBinomialQueue(c);
        deletedQueue.size = (1 << minIndex) - 1;
        for (int j = minIndex - 1; j >= 0; j--) {
            deletedQueue.trees[j] = deletedTree;
            deletedTree = deletedTree.nextSibling;
            deletedQueue.trees[j].nextSibling = null;
        }
        trees[minIndex] = null;
        size -= deletedQueue.size + 1;

        try {
            meld(deletedQueue);
        } catch (Exception e) {
        }
        return minItem;
    }

    @Override
    public void insert(Type object) {
        MyBinomialQueue oneItem = new MyBinomialQueue(c);
        oneItem.size = 1;
        oneItem.trees[0] = new BinomialNode(object);
        meld(oneItem);
    }

    @Override
    public BinomialQueue<Type> meld(BinomialQueue<Type> bq) {
        if (this.equals(bq)) {
            return this;
        }
        if (size + bq.size() > capacity()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        MyBinomialQueue bq1 = (MyBinomialQueue) bq;
        size += bq1.size();

        BinomialNode carry = null;
        for (int i = 0, j = 1; j <= size; i++, j *= 2) {
            BinomialNode t1 = trees[i];
            BinomialNode t2 = bq1.trees[i];
            int whichcase = t1 == null ? 0 : 1;
            whichcase += t2 == null ? 0 : 2;
            whichcase += carry == null ? 0 : 4;

            switch (whichcase) {
                case 0: //No hay árboles
                case 1: //Sólo este
                    break;
                case 2: //Sólo bq
                    trees[i] = t2;
                    bq1.trees[i] = null;
                    break;
                case 3:
                    carry = combineTrees(t1,t2);
                    trees[i] = bq1.trees[i] = null;
                    break;
                case 4:
                    trees[i] = carry;
                    carry = null;
                    break;
                    
                case 5: 
                    carry = combineTrees(t1,carry);
                    trees[i] = null;
                    break;
                case 6:
                    carry = combineTrees(t2,carry);
                    bq1.trees[i] = null;
                    break;
                case 7:
                    trees[i] = carry;
                    carry = combineTrees(t1, t2);
                    bq1.trees[i] = null;
                    break;

            }
        }
        for(int k=0;k<bq1.trees.length;k++){
            bq1.trees[k] = null;
        }
        bq1.size = 0;

        return this;
    }

    private BinomialNode combineTrees(BinomialNode t1, BinomialNode t2) {
        if (c.compare(t1.element, t2.element) > 0) {
            return combineTrees(t2, t1);
        }
        t2.nextSibling = t1.leftChild;
        t1.leftChild = t2;
        return t1;
    }

    private int capacity() {
        return (1 << trees.length) - 1;
    }

    @Override
    public String toString() {
        String toString = "Contiene un total de "+size+" arboles en la cola binomial";
        
        return toString;
    }
}
